#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<vector>
using namespace std;
#define ElemType int
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
LNode* InitList(LinkList L)
{
	cout<<"初始化单链表"<<'\n'; //初始化链表
	L=new LNode;
	L->next=NULL;
	cout<<"初始化成功"<<'\n'; //初始化成功
	return L;
}
void ListInsert(LinkList L,ElemType a,int n)
{
    LNode *p=new LNode;
    LNode* q=new LNode;
    p=L;
    int i=0;
    while(p&&i++!=n-1)
    {
        p=p->next;
    }
    q->data=a;
    q->next=p->next;
    p->next=q;
    
}
void DispList(LinkList L)
{
	
	LNode *p=new LNode;
	p=L->next;
	while(p)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<'\n';

}
vector<ElemType> Intersection(LinkList L1,LinkList L2)
{
    cout<<"输出单链表La和Lb的交集"<<'\n';
    LNode *p=new LNode;
    LNode *q=new LNode;
    p=L1->next;
    q=L2->next;
    vector<ElemType>vec;
   while(p!=NULL)
    {   
        
         while(q!=NULL)
         {  
            
            if(q->data==p->data)
            {
                
                vec.push_back(q->data);
                break; 
            }
            q=q->next;
         }
         q=L2->next;
         p=p->next;
    }
    for(auto e:vec)
    {
        cout<<e<<' ';
    }
    cout<<'\n';
    return vec;
}
void Union(LinkList L1,LinkList L2)
{
    cout<<"输出单链表La和Lb的并集"<<'\n';
    vector<ElemType>vec;
    LNode *p=new LNode;
    LNode *q=new LNode;
    p=L1->next;
    q=L2->next;
    bool flag=0;
    while(p!=NULL)
    {   
        flag=0;
         while(q!=NULL)
         {  
            
            if(q->data==p->data)
            {
                flag=1;
                break; 
            }
            q=q->next;
         }
         if(flag==0)
        vec.push_back(p->data);
         q=L2->next;
         p=p->next;
    }
    q=L2->next;
    while(q!=NULL)
    {
        vec.push_back(q->data);
        q=q->next;
    }
    for(auto e:vec)
    {
        cout<<e<<' ';

    }
    cout<<'\n';
    return;
}
void Differenceset(LinkList L1,vector<ElemType>vec1)
{
    LNode*p=new LNode;
    p=L1->next;
    vector<ElemType>vec;
    bool flag=0;
    while(p)
    {
        flag=0;
        for(int i=0;i<vec1.size();i++)
        {
            if(vec1[i]==p->data)
            {
                flag=1;
                break;
            }

        }
        if(flag==0)
        vec.push_back(p->data);
        p=p->next;
    }
    for(auto e:vec)
    {
        cout<<e<<' ';
    }
    cout<<'\n';
    return ;
}
int main()
{
    LinkList La;
    LinkList Lb;
    La=InitList(La);
    Lb=InitList(Lb);
    vector<ElemType>vec1;
    char c;
    int a,n;
    cout<<"输入插入单链表La的元素"<<'\n';
    while(c!='\n')
    {
        c=getchar();
        if(c!=' '&&c!='\n')
        ListInsert(La,(int)(c-'0'),1);//头插法6 1 3 4
    }
    cout<<"输出单链表La"<<'\n';
    DispList(La);
    cout<<"输入插入Lb的元素"<<'\n';
    c=' ';
    while(c!='\n')
    {
        c=getchar();
        if(c!=' '&&c!='\n')
        ListInsert(Lb,(int)(c-'0'),1);//头插法7 6 3 2

    }
    cout<<"输出单链表Lb"<<'\n';
    DispList(Lb);
    vec1=Intersection(La,Lb);
    Union(La,Lb);
    cout<<"输出单链表La与Lb的差集"<<'\n';
    Differenceset(La,vec1);
    cout<<"输出单链表Lb与La的差集"<<'\n';
    Differenceset(Lb,vec1);
    system("pause");
    return 0;
}